1. Field of the Invention
The disclosure relates generally to a method and system for replacing an entry in a cache, and more specifically to using the method and system to implement a multiple-class priority-based replacement policy for a cache memory.
2. Description of the Related Art
Modern computer systems employ cache memories in addition to main memory. The access latency of cache memory is significantly less than the access latency of main memory. One type of these cache memories retains recently accessed data, in the presumption that this data will be accessed again in the future. A second type of these cache memories retains recently accessed instructions. A third type of these cache memories retains recently accessed mappings of virtual to physical addresses; such a cache is referred to as a Translation Lookaside Buffer (TLB). A valid cache entry in a data cache or instruction cache references a page in memory where the data or instruction is stored. An entry in a TLB also references a page in memory as the address translation stored in an entry of the TLB identifies a specific page in memory.
Memory operations performed by a processor access cache memory first. For example, an action such as read, write or execute, is requested to be performed at a page in memory. The processor translates, if necessary, the page address within a TLB. Then the processor looks to a data or instruction cache to see if information from the referenced page may be found there. In the event that the accessed data, instruction, or address is not found in the cache (termed a cache miss), the processor must wait for an extended period of time while that data, instruction, or address is loaded into the cache from a slower or more remote memory. Processor stalls caused by this wait period comprise the majority of execution time for many applications.
A cache memory is logically organized as a set of cache entries. When a cache miss occurs, the cache in which a new entry is to be placed is first examined; if that cache is full, room must be created for the new entry by evicting one of the currently residing entries from the cache. This entry selected for eviction is termed the victim. Many techniques have been developed to determine the best choice of victim, such that the miss rate to the cache will be minimized. These are known in the art as replacement policies. Examples include least-recently used (LRU) algorithms and First-In First-Out (FIFO) algorithms. These replacement policies have been designed to minimize the frequency of misses to the cache.
A TLB may comprise a Content Addressable Memory (CAM) and associated Random Access Memory (RAM), each having a fixed number of entries. The CAM performs a parallel comparison of a virtual page number presented for translation, against all stored, previously translated virtual page numbers. The output of the CAM is the location of the stored virtual page number that matches the applied virtual page number. This location indexes the RAM, which provides the stored physical page number corresponding to the virtual page number, as well as the page attributes. The physical address applied to the cache and/or main memory is then the physical page number retrieved from the TLB, concatenated with the page offset from the virtual address.
When a TLB miss occurs, the processor must traverse page tables to perform a translation (page walk). When the page walk is complete, the virtual and physical page numbers and page attributes are stored in an empty entry in the TLB. If the TLB is full, an entry must be victimized. Replacement policies for this victimization include random, round-robin, not recently used, second-chance FIFO, and the like. Some policies, such as the not recently used, may identify different types of entries with identification bits, but clear all identification at a set time or pre-defined occurrence.
The design of TLBs, in particular first-level TLBs, is constrained by area, power, and cycle-time. The need to have 0-cycle access times (or as near as possible) forces these structures to be small. To maximize hit rate and avoid constraining which pages can coexist in the TLB, these structures also tend to be fully associative. In addition, these structures are often replicated to increase read bandwidth so they can be accessed concurrently by different ports. The highly associative nature of TLBs, combined with short access times and the difficulty of combining history information from multiple reference streams makes LRU-type replacement policies costly and infeasible. For example, LRU replacement requires an update with every access, a complicated order-list to be maintained to keep track of when each entry was accessed, and if there are many copies of the cache, multiplied complexity. Hence, many first-level TLBs tend to use simple replacement policies such as a FIFO replacement policy due to simplicity of implementation and low overhead.